//https://leetcode.cn/problems/partition-list-lcci/description/
//分割链表
//给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
//你不需要 保留 每个分区中各节点的初始相对位置。

typedef struct ListNode ListNode;

struct ListNode* partition(struct ListNode* head, int x){
    if(head == NULL||head->next == NULL)
    return head;

    ListNode* lesshead = (ListNode*)malloc(sizeof(ListNode));
    ListNode* greaterhead = (ListNode*)malloc(sizeof(ListNode));
    ListNode* lesstail = lesshead, *greatertail = greaterhead;
    ListNode* pcur = head;
    while(pcur != NULL)
    {
        if(pcur->val < x)
        {
            lesstail->next = pcur;
            lesstail = lesstail->next;
        }
        else
        {
            greatertail->next = pcur;
            greatertail = greatertail->next;
        }
        pcur = pcur->next;
    }
    greatertail->next = NULL;
    lesstail->next = greaterhead->next;

    ListNode* ret = lesshead->next;
    free(lesshead);
    free(greaterhead);

    return ret;
}
